\subsection{Filtro Sierpinski}

El filtro, basado en el conjunto fractal de Wacław Sierpiński, tiene como objetivo generar un efecto fractálico sobre la imagen fuente, mediante el calculo de un coeficiente que se aplica sobre cada pixel.


En aras de no perder exactitud y poder realizar todas las operaciones contenidas en el coeficiente, el pasaje a punto flotante de precisi\'on simple, entero y caracter sin signo es demandado. Pasaje, que se pone de manifiesto m\'as nitidamente en la implementaci\'on en ASM.


\subsubsection{Implementaci\'on en C}

La implementaci\'on en C consiste en un doble ciclo anidado, en donde para cada indice de fila y columna de pixeles, se calcula un coeficiente que se aplica a cada byte R, G, B, A para generar la imagen de destino. 

El pseudoc\'odigo es el siguiente:

\begin{codesnippet}
\begin{verbatim}

    Para i = 0 hasta el Alto de la Imagen Fuente; Paso: i++
    	    k = -1
        Para j = 0 hasta Ancho de la Imagen Fuente * 4 ; Paso: j ++
        
        	  Si (j mod 4 = 0)
              k ++
            	 Calcular el coeficiente
       	   Fin Si
           
           Escribir en la posicion(i, j) de la matriz de la imagen destino, 
           el componente (i, j) de la matriz de la imagen fuente * el coeficiente
		
        Fin Para
    Fin Para
\end{verbatim}
\end{codesnippet}



\subsubsection{Implementaci\'on en ASM}

La implementaci\'on en ASM presenta mucha similitudes con respecto a la implementaci\'on en C (doble ciclo anidado que recorre toda la imagen fuente), con la excepci\'on, considerable, de que en ASM se trabaja con 4 pixeles (16 bytes) en una misma iteraci\'on de ciclo.

En el codigo se usa EAX como contador para la cantidad de filas (i) y RDX como contador para el recorrido por las columnas de a bytes (j), manteniendo en EBX la posicion de columnas de pixeles (k).
Antes de iniciar  los ciclos, se reserva el registro XMM6 para guardar el valor del calculo 1/255.0 , esto se hace mediante el siguiente código asm:
\begin{verbatim}
MOVD XMM2, rows ; XMM2 = | 0 | 0 | 0 | rows |
PSHUFD XMM2, XMM2, 0H ; XMM2 = | rows | rows | rows | rows |
CVTDQ2PS XMM2, XMM2
MOVD XMM3, EDX ; XMM3 = | * | * | * | cols |
PSHUFD XMM3, XMM3, 0H ; XMM3 = | cols | cols | cols | cols |
CVTDQ2PS XMM3, XMM3 
MOVDQU XMM4, [MAXIMOPIXELES] ; XMM4 = | 255.0 | 255.0 | 255.0 | 255.0 |
MOVD XMM6, [UNO] ; XMM6 = | * | * | * | 1 |
PSHUFD XMM6, XMM6, 0H ; XMM6 = | 1 | 1 | 1 | 1 |
CVTDQ2PS XMM6, XMM6
DIVPS XMM6, XMM4 ; XMM6 = | 1 / 255.0 | 1 / 255.0 | 1 / 255.0 | 1 / 255.0 |
\end{verbatim}
Se trata nuevamente de un doble ciclo anidado, por filas y columnas. El procesamiento se hace de a 16 bytes (4 pıxeles). En cada iteraci\'on se realiza lo siguiente:
\begin{itemize}
	\item En el ciclo de la fila, se reinicia los contadores de las columnas y se calcula parte del coeficiente:
\begin{verbatim}
 XOR RDX, RDX ;
 XOR RBX, RBX ;
 MOVD XMM1, EAX  ; XMM1 = | * | * | * | i |
 PSHUFD XMM1, XMM1, 0H ; XMM1 = | i | i | i | i|
 CVTDQ2PS XMM1, XMM1
 DIVPS XMM1, XMM2 ; XMM1 = | i / rows | i / rows | i / rows | i / rows |
 MULPS XMM1, XMM4 ; XMM1 = | (i / rows) * 255.0 | (i / rows) * 255.0 | 
 (i / rows) * 255.0 | (i / rows) * 255.0 |
 CVTTPS2DQ XMM1, XMM1
\end{verbatim}    
	\item Dentro del ciclo de la columna, de XMM7 al XMM10 se calculan los coeficientes (para cada valor de columna de pixel), mediante el siguiente código asm:
\begin{verbatim}
MOVD XMM5, EBX  ; XMM5 = | * | * | * | k |
PSHUFD XMM5, XMM5, 0H ; XMM5 = | k | k | k | k |
CVTDQ2PS XMM5, XMM5
DIVPS XMM5, XMM3 ; XMM5 = | k / cols | k / cols | k / cols | k / cols |
MULPS XMM5, XMM4 ; XMM5 = | (k / cols) * 255.0 | (k / cols) * 255.0 
| (k / cols) * 255.0 | (k / cols) * 255.0 |
CVTTPS2DQ XMM5, XMM5 
MOVDQU XMM7, XMM1
PXOR XMM7, XMM5 ; XMM7 = ((int)(i / rows) * 255.0) XOR ((int)(k / cols) * 255.0))
CVTDQ2PS XMM7, XMM7
MULPS XMM7, XMM6  ; XMM7 = (1 / 255.0) * ((i / rows) * 255.0) XOR ((k / cols) * 255.0)
\end{verbatim} 
	\item Una vez calculados los coeficientes, se pasa a obtener los pixeles a cambiar mediante la instrucción \textit{MOVDQU}, siendo necesario pasar la informacion de tamaño byte a tamaño dword. Este pasaje se logra mediante el uso de las intrucciones para desempaquetar, \textit{PUNPCKLBW} y \textit{PUNPCKLHBW} (de byte a word), y \textit{PUNPCKLWD} y \textit{PUNPCKLHWD} (de word a dword), teniendo los datos de cada pixel en un registro XMM separado. En XMM0 los datos del primer pixel , en XMM13 los datos del segundo pixel, en XMM11 los datos del tercer pixel y en XMM12 los datos del cuarto pixel.
	\item Luego usando la instrucci\'on \textit{CVTDQ2PS} se obtiene la informaci\'on en punto flotante de precisi\'on simple.
	\item Se realiza la multiplicacion de cada pixel por su coeficiente correspondiente, XMM0 por XMM1, XMM13 por XMM8, XMM11 por XMM9 y XMM12 por XMM10.  para luego hacer un pasaje a entero, mediante \textit{CVTTPS2DQ}.
	\item Por ultimo se empaqueta la informacı\'on mediante las instrucciones \textit{PACKUSDW} y \textit{PACKUSWB}, para tener 16 bytes en un registro XMM0, y asi mover los bytes modificados a la imagen.
\end{itemize}

\newpage

\subsubsection{Experimentos y An\'alisis de resultado}
%algo
%\\
%\\
\textbf{Experimento 1 - "secuencial vs vectorial"}

Las mediciones para este filtro se realizaron en una computadora con un procesador Intel i3 con dos core y 4 threads.

El experimento se realiz\'o utilizando imagenes cuyo tamaño son de 200x200,  512x512 y 1024x767.
A continuac\'ion se muestra un grafico, el cual compara la performance de la versi\'on ASM, y las versiones C optimazadas en -O0, -O1, -O2 y -O3. La idea del mismo, es mostrar cuanto m\'as tardan las versiones C con respecto a la versi\'on ASM en terminos porcentuales.
\begin{figure}[H]
  \begin{center}
   \includegraphics[scale=0.66]{imagenes/grafico2-1.png}
  \end{center}
\end{figure}

El siguiente gr\'afico muestra los valores absolutos de la performance de cada implementac\'ion:
\begin{figure}[H]
  \begin{center}
   \includegraphics[scale=0.66]{imagenes/grafico2-2.png}
  \end{center}
\end{figure}

La informaci\'on con la cual se confeccion\'o los gr\'aficos es la siguiente (los valores se refieren a cantidad de ciclos de reloj):
\\

    \begin{tabular}{ | l | l | l | l | l | l |}
    \hline
	Dimensi\'on & ASM & -O0 & -01 & -O2 & -O3 \\ \hline
	Promedio 200x200 & 741.456
& 4.549.816 &4.646.898
 & 4.197.479
 & 4.235.930
 \\ \hline
	Promedio 512x512 & 3.698.281
 & 26.589.727
 & 24.138.039
 & 24.283.849
 & 24.483.007
\\ \hline
	Promedio 1024x767 & 11.065.430
 & 82.889.573
 & 77.253.041
 & 77.841.676
 & 77.317.364
\\ \hline
    \end{tabular}
\\
\\
Esta informaci\'on pone de manifiesto la diferencia considerable de performance entre ambas implementaciones, m\'as alla de las optimizaciones.

Con respecto a la varianza, los valores que arrojaron las mediciones son los siguientes:
\\

    \begin{tabular}{ | l | l | l | l | l | l |}
    \hline
	Dimensi\'on & ASM & -O0 & -01 & -O2 & -O3 \\ \hline
	Var 200x200 & 108.975.989
 & 116.821.765
 & 74.956.567.076
 & 494.984.808
 & 1.267.170.321
 \\ \hline
	Var 512x512 & 15.440.444.980
 & 583.879.790
 & 174.676.013
 & 572.351.826
 & 6.965.772.590
\\ \hline
	Var 1024x767 & 21.887.397.636
 & 21.956.313.337
 & 24.613.550.857
 & 638.934.565
 & 61.940.079.363
\\ \hline
    \end{tabular}
\\
\\
Su correspondiente gr\'afico es el siguiente:
\begin{figure}[H]
  \begin{center}
   \includegraphics[scale=0.66]{imagenes/grafico2-3.png}
  \end{center}
\end{figure}

\textbf{Experimento 2 - "secuencial vs vectorial"}

En el siguiente experimento usamos la misma l\'ogica que se aplic\'o en el filtro cropflip. En este caso usamos una imagen de 200x200. 

Los resultados, expresados en cantidad de ciclos adicionales con respecto a la versi\'on original, fueron los siguientes:
\\
\\
    \begin{tabular}{ | l | l | l |}
    \hline
	 Cantidad de instrucciones adicionales & Instrucciones aritm\'eticas & Instrucciones de memoria \\ \hline
4 & 41.539 & 77.131 \\ \hline
8 & 500.953 & 627.351 \\ \hline
16 & 710.154 & 800.507 \\ \hline
    \end{tabular}
\\
\\
Graficamente, en terminos de incremento porcentual:
\begin{figure}[H]
  \begin{center}
   \includegraphics[scale=0.66]{imagenes/grafico2-4.png}
  \end{center}
\end{figure}



Graficamente, en valores absolutos:
\begin{figure}[H]
  \begin{center}
   \includegraphics[scale=0.66]{imagenes/grafico2-5.png}
  \end{center}
\end{figure}

Los gr\'aficos se confeccionaron con la siguiente informaci\'on:
\\

    \begin{tabular}{ | l | l | l | l | l | l |}
    \hline
	Cant instrucciones agregadas & 4 & 8 & 16 \\ \hline
	Original & 741.456
& 741.456 & 741.456
 \\ \hline
	Aritmeticas & 782.995
 & 1.242.409
 & 1.451.610
\\ \hline
	Acceso memoria & 818.587
 & 1.368.807
 & 1.541.963
\\ \hline
    \end{tabular}
\\
\\


Los datos arrojan un mayor peso de las instrucciones de memoria del uso de bus, sin embargo al ser la diferencia tan escasa, no es posible concluir que estas instrucciones tienen una mayor incidencia en la performance del filtro.
 
En este filtro, estas pruebas fueron realizadas en un equipo con la siguiente jerarqu\'ias de cache:

\begin{verbatim}

salida de dmidecode -t cache

ache Information
	Socket Designation: Unknown
	Configuration: Enabled, Not Socketed, Level 1
	Operational Mode: Write Back
	Location: Internal
	Installed Size: 32 kB
	Maximum Size: 32 kB
	Supported SRAM Types:
		Asynchronous
	Installed SRAM Type: Asynchronous
	Speed: Unknown
	Error Correction Type: Single-bit ECC
	System Type: Data
	Associativity: 8-way Set-associative

Handle 0x0002, DMI type 7, 19 bytes
Cache Information
	Socket Designation: Unknown
	Configuration: Enabled, Not Socketed, Level 2
	Operational Mode: Write Back
	Location: Internal
	Installed Size: 256 kB
	Maximum Size: 256 kB
	Supported SRAM Types:
		Asynchronous
	Installed SRAM Type: Asynchronous
	Speed: Unknown
	Error Correction Type: Single-bit ECC
	System Type: Unified
	Associativity: 8-way Set-associative

 
\end{verbatim}


La l\'inea de cache en este ambiente de pruebas tiene un tamaño de 64 bytes. N\'otese entonces que la cache L1, por ser asociativa por 8 v\'ias, tiene 4Kb por conjunto (tamaño total de 32Kb). Si el tamaño de l\'inea de la cache es de 64 bytes, tenemos que cada l\'inea tiene 64 bytes. Para generar m\'as misses en la cache de L1 lo que se hizo fue realizar operaciones de acceso a memoria subiendo en la pila de a 64 bytes. As\'i las instrucciones que se ejecutaron en cada iteraci\'on son las siguientes (empezando con R8 en 0 y rest\'andole 64 bytes en cada paso del ciclo)

\begin{verbatim}
    SUB R8, 64
    MOV [RSP + R8], R9
    MOV R9, [RSP + R8]
    MOV [RSP + R8], R9
    MOV R9, [RSP + R8]
    MOV [RSP + R8], R9
    MOV R9, [RSP + R8]
    MOV [RSP + R8], R9
    MOV R9, [RSP + R8]
    MOV [RSP+ R8], R9
    MOV R9, [RSP + R8]
    MOV [RSP + R8], R9
    MOV R9, [RSP + R8]
    MOV [RSP + R8], R9
    MOV R9, [RSP + R8]
    MOV [RSP + R8], R9
    MOV R9, [RSP + R8]
    MOV [RSP + R8], R9
    MOV R9, [RSP + R8]
\end{verbatim}














